home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqbuild / surfaces.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  10.9 KB  |  505 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. #define    NUM_HASH    4096
  5.  
  6. typedef struct hashvert_s {
  7.   struct hashvert_s *next;
  8.   vec3_t point;
  9.   int num;
  10.   int numplanes;                                   // for corner determination
  11.  
  12.   int planenums[2];
  13.   int numedges;    
  14. } __packed hashvert_t;                // 36
  15.  
  16. /* changed by niels */
  17. #ifdef DEBUG
  18. hashvert_t hvertex[MAX_MAP_VERTS];        // 847872
  19. hashvert_t *hvert_p;                // 4
  20. #endif
  21.  
  22. int firstmodeledge = 1;                // 4
  23. int firstmodelface;                // 4
  24.  
  25. hashvert_t *hashverts[NUM_HASH];        // 16384
  26. int c_cornerverts;            // 4
  27. int c_tryedges;                // 4
  28. int subdivides;
  29. vec3_t hash_min, hash_scale;        // 24
  30. struct surface newcopy_t;        // 48
  31.  
  32. /*
  33.  * a surface has all of the faces that could be drawn on a given plane
  34.  * 
  35.  * the outside filling stage can remove some of them so a better bsp can be generated
  36.  * 
  37.  */
  38.  
  39. //============================================================================
  40.  
  41. /*
  42.  * ===============
  43.  * SubdivideFace
  44.  * 
  45.  * If the face is >256 in either texture direction, carve a valid sized
  46.  * piece off and insert the remainder in the next link
  47.  * ===============
  48.  */
  49. void SubdivideFace(__memBase, register struct visfacet * f, register struct visfacet ** prevptr)
  50. {
  51.   float mins, maxs;
  52.   vec_t v;
  53.   short int axis;
  54.   int i;
  55.   struct plane plane;
  56.   struct visfacet *front, *back, *next;
  57.   struct texinfo *tex;
  58.  
  59. // special (non-surface cached) faces don't need subdivision
  60.   tex = &bspMem->texinfo[f->texturenum];
  61.  
  62.   if (tex->flags & TEX_SPECIAL)
  63.     return;
  64.  
  65.   for (axis = 0; axis < 2; axis++) {
  66.     while (1) {
  67.       mins = 9999;
  68.       maxs = -9999;
  69.  
  70.       for (i = 0; i < f->numpoints; i++) {
  71.     v = DotProduct(f->pts[i], tex->vecs[axis]);
  72.     if (v < mins)
  73.       mins = v;
  74.     if (v > maxs)
  75.       maxs = v;
  76.       }
  77.  
  78.       if (maxs - mins <= subdivide_size)
  79.     break;
  80.  
  81.       // split it
  82.       subdivides++;
  83.  
  84.       VectorCopy(tex->vecs[axis], plane.normal);
  85.       v = VectorLength(plane.normal);
  86.       VectorNormalize(plane.normal);
  87.       plane.dist = (mins + subdivide_size - 16) / v;
  88.       next = f->next;
  89.       SplitFace(f, &plane, &front, &back);
  90.       if (!front || !back)
  91.     Error("SubdivideFace: didn't split the polygon");
  92.       *prevptr = back;
  93.       back->next = front;
  94.       front->next = next;
  95.       f = back;
  96.     }
  97.   }
  98. }
  99.  
  100. /*
  101.  * ================
  102.  * SubdivideFaces
  103.  * ================
  104.  */
  105. void SubdivideFaces(__memBase, register struct surface * surfhead)
  106. {
  107.   struct surface *surf;
  108.   struct visfacet *f, **prevptr;
  109.  
  110.   mprintf("----- SubdivideFaces ---\n");
  111.  
  112.   subdivides = 0;
  113.  
  114.   for (surf = surfhead; surf; surf = surf->next) {
  115.     prevptr = &surf->faces;
  116.     while (1) {
  117.       f = *prevptr;
  118.       if (!f)
  119.     break;
  120.       SubdivideFace(bspMem, f, prevptr);
  121.       f = *prevptr;
  122.       prevptr = &f->next;
  123.     }
  124.   }
  125.  
  126.   mprintf("%i faces added by subdivision\n", subdivides);
  127.  
  128. }
  129.  
  130. /*
  131.  * =============================================================================
  132.  * 
  133.  * GatherNodeFaces
  134.  * 
  135.  * Frees the current node tree and returns a new chain of the surfaces that
  136.  * have inside faces.
  137.  * =============================================================================
  138.  */
  139.  
  140. void GatherNodeFaces_r(register struct node * node)
  141. {
  142.   struct visfacet *f, *next;
  143.  
  144.   if (node->planenum != PLANENUM_LEAF) {
  145. //
  146.     // decision node
  147.     //
  148.     for (f = node->faces; f; f = next) {
  149.       next = f->next;
  150.       if (!f->numpoints) {                               // face was removed outside
  151.  
  152.     FreeFace(f);
  153.       }
  154.       else {
  155.     f->next = validfaces[f->planenum];
  156.     validfaces[f->planenum] = f;
  157.       }
  158.     }
  159.  
  160.     GatherNodeFaces_r(node->children[0]);
  161.     GatherNodeFaces_r(node->children[1]);
  162.  
  163.     tfree(node);
  164.   }
  165.   else {
  166. //
  167.     // leaf node
  168.     //
  169.     tfree(node);
  170.   }
  171. }
  172.  
  173. /*
  174.  * ================
  175.  * GatherNodeFaces
  176.  * 
  177.  * ================
  178.  */
  179. struct surface *GatherNodeFaces(__memBase, register struct node * headnode)
  180. {
  181.   struct surface *returnval;
  182.  
  183.   /* added by niels */
  184.   if(!(validfaces = (struct visfacet **)tmalloc(sizeof(struct visfacet *) * bspMem->numbrushplanes)))
  185.     Error("GatherNodeFaces: failed to allocate validfaces\n");
  186.   GatherNodeFaces_r(headnode);
  187.   returnval = BuildSurfaces(bspMem);
  188.   /* added by niels */
  189.   tfree(validfaces);
  190.   return returnval;
  191. }
  192.  
  193. //===========================================================================
  194.  
  195. void InitHash(void)
  196. {
  197.   vec3_t size;
  198.   vec_t volume;
  199.   vec_t scale;
  200.   int newsize[2];
  201.   short int i;
  202.  
  203.   memset(hashverts, 0, sizeof(hashverts));
  204.  
  205.   for (i = 0; i < 3; i++) {
  206.     hash_min[i] = -8000;
  207.     size[i] = 16000;
  208.   }
  209.  
  210.   volume = size[0] * size[1];
  211.  
  212.   scale = sqrt(volume / NUM_HASH);
  213.  
  214.   newsize[0] = size[0] / scale;
  215.   newsize[1] = size[1] / scale;
  216.  
  217.   hash_scale[0] = newsize[0] / size[0];
  218.   hash_scale[1] = newsize[1] / size[1];
  219.   hash_scale[2] = newsize[1];
  220.  
  221.   /* changed by niels */
  222. #ifdef DEBUG
  223.   hvert_p = hvertex;
  224. #endif
  225. }
  226.  
  227. unsigned HashVec(register vec3_t vec)
  228. {
  229.   unsigned h;
  230.  
  231.   h = hash_scale[0] * (vec[0] - hash_min[0]) * hash_scale[2]
  232.     + hash_scale[1] * (vec[1] - hash_min[1]);
  233.   if (h >= NUM_HASH)
  234.     return NUM_HASH - 1;
  235.   return h;
  236. }
  237.  
  238. /*
  239.  * =============
  240.  * GetVertex
  241.  * =============
  242.  */
  243. int GetVertex(__memBase, register vec3_t in, register int planenum)
  244. {
  245.   int h;
  246.   int i;
  247.   hashvert_t *hv;
  248.   vec3_t vert;
  249.  
  250.   for (i = 0; i < 3; i++) {
  251.     if (fabs(in[i] - rint(in[i])) < 0.001)
  252.       vert[i] = rint(in[i]);
  253.     else
  254.       vert[i] = in[i];
  255.   }
  256.  
  257.   h = HashVec(vert);
  258.  
  259.   for (hv = hashverts[h]; hv; hv = hv->next) {
  260.     if (fabs(hv->point[0] - vert[0]) < POINT_EPSILON
  261.     && fabs(hv->point[1] - vert[1]) < POINT_EPSILON
  262.     && fabs(hv->point[2] - vert[2]) < POINT_EPSILON) {
  263.       hv->numedges++;
  264.       if (hv->numplanes == 3)
  265.     return hv->num;                                   // allready known to be a corner
  266.  
  267.       for (i = 0; i < hv->numplanes; i++)
  268.     if (hv->planenums[i] == planenum)
  269.       return hv->num;                               // allready know this plane
  270.  
  271.       if (hv->numplanes == 2)
  272.     c_cornerverts++;
  273.       else
  274.     hv->planenums[hv->numplanes] = planenum;
  275.       hv->numplanes++;
  276.       return hv->num;
  277.     }
  278.   }
  279.  
  280.   /* changed by niels */
  281.   //hv = hvert_p;
  282.   if(!(hv = (hashvert_t *)kmalloc(sizeof(hashvert_t))))
  283.     Error("GetVertex: failed to allocate hashvert!\n");
  284.   hv->numedges = 1;
  285.   hv->numplanes = 1;
  286.   hv->planenums[0] = planenum;
  287.   hv->next = hashverts[h];
  288.   hashverts[h] = hv;
  289.   VectorCopy(vert, hv->point);
  290.   if (bspMem->numvertexes == bspMem->max_numvertexes)
  291.     ExpandClusters(bspMem, LUMP_VERTEXES);
  292.   hv->num = bspMem->numvertexes;
  293.   /* changed by niels */
  294.   //hvert_p++;
  295.  
  296. // emit a vertex
  297.   if (bspMem->numvertexes == bspMem->max_numvertexes)
  298.     ExpandClusters(bspMem, LUMP_VERTEXES);
  299.  
  300.   bspMem->dvertexes[bspMem->numvertexes].point[0] = vert[0];
  301.   bspMem->dvertexes[bspMem->numvertexes].point[1] = vert[1];
  302.   bspMem->dvertexes[bspMem->numvertexes].point[2] = vert[2];
  303.   bspMem->numvertexes++;
  304.  
  305.   return hv->num;
  306. }
  307.  
  308. //===========================================================================
  309.  
  310. /*
  311.  * ==================
  312.  * GetEdge
  313.  * 
  314.  * Don't allow four way edges
  315.  * ==================
  316.  */
  317.  
  318. int GetEdge(__memBase, register vec3_t p1, register vec3_t p2, register struct visfacet * f)
  319. {
  320.   int v1, v2;
  321.   struct dedge_t *edge;
  322.   int i;
  323.  
  324.   if (!f->contents[0])
  325.     Error("GetEdge: 0 contents");
  326.  
  327.   c_tryedges++;
  328.   v1 = GetVertex(bspMem, p1, f->planenum);
  329.   v2 = GetVertex(bspMem, p2, f->planenum);
  330.   for (i = firstmodeledge; i < bspMem->numedges; i++) {
  331.     edge = &bspMem->dedges[i];
  332.     if (v1 == edge->v[1] && v2 == edge->v[0]
  333. /*    && !edgefaces[i][1] */
  334.     && !bspMem->edgefaces[1][i]
  335. /*    && edgefaces[i][0]->contents[0] == f->contents[0]) { */
  336.     && bspMem->edgefaces[0][i]->contents[0] == f->contents[0]) {
  337. /*    edgefaces[i][1] = f; */
  338.       bspMem->edgefaces[1][i] = f;
  339.       return -i;
  340.     }
  341.   }
  342.  
  343. // emit an edge
  344.   if (bspMem->numedges == bspMem->max_numedges)
  345.     ExpandClusters(bspMem, LUMP_EDGES);
  346.   edge = &bspMem->dedges[bspMem->numedges];
  347.   bspMem->numedges++;
  348.   edge->v[0] = v1;
  349.   edge->v[1] = v2;
  350. /*edgefaces[i][0] = f; */
  351.   bspMem->edgefaces[0][i] = f;
  352.  
  353.   return i;
  354. }
  355.  
  356. /*
  357.  * ==================
  358.  * FindFaceEdges
  359.  * ==================
  360.  */
  361. void FindFaceEdges(__memBase, register struct visfacet * face)
  362. {
  363.   int i;
  364.  
  365.   face->outputnumber = -1;
  366.   if (face->numpoints > MAXEDGES)
  367.     Error("WriteFace: %i points", face->numpoints);
  368.  
  369.   for (i = 0; i < face->numpoints; i++)
  370.     face->edges[i] = GetEdge(bspMem, face->pts[i], face->pts[(i + 1) % face->numpoints], face);
  371. }
  372.  
  373. #ifdef DEBUG
  374. /*
  375.  * =============
  376.  * CheckVertexes
  377.  * // debugging
  378.  * =============
  379.  */
  380. void CheckVertexes(void)
  381. {
  382.   int cb, c0, c1, c2, c3;
  383.   hashvert_t *hv;
  384.  
  385.   cb = c0 = c1 = c2 = c3 = 0;
  386.   for (hv = hvertex; hv != hvert_p; hv++) {
  387.     if (hv->numedges < 0 || hv->numedges & 1)
  388.       cb++;
  389.     else if (!hv->numedges)
  390.       c0++;
  391.     else if (hv->numedges == 2)
  392.       c1++;
  393.     else if (hv->numedges == 4)
  394.       c2++;
  395.     else
  396.       c3++;
  397.   }
  398.  
  399.   mprintf("%5i bad edge points\n", cb);
  400.   mprintf("%5i 0 edge points\n", c0);
  401.   mprintf("%5i 2 edge points\n", c1);
  402.   mprintf("%5i 4 edge points\n", c2);
  403.   mprintf("%5i 6+ edge points\n", c3);
  404. }
  405.  
  406. /*
  407.  * =============
  408.  * CheckEdges
  409.  * // debugging
  410.  * =============
  411.  */
  412. void CheckEdges(void)
  413. {
  414.   struct dedge_t *edge;
  415.   int i;
  416.   struct dvertex_t *d1, *d2;
  417.   struct visfacet *f1, *f2;
  418.   int c_nonconvex;
  419.   int c_multitexture;
  420.  
  421.   c_nonconvex = c_multitexture = 0;
  422.  
  423.   //      CheckVertexes ();
  424.  
  425.   for (i = 1; i < bspMem->numedges; i++) {
  426.     edge = &bspMem->dedges[i];
  427. /*    if (!edgefaces[i][1]) { */
  428.       if (!bspMem->edgefaces[1][i]) {
  429.       d1 = &bspMem->dvertexes[edge->v[0]];
  430.       d2 = &bspMem->dvertexes[edge->v[1]];
  431.       mprintf("unshared edge at: ( %g %g %g ) ( %g %g %g )\n", d1->point[0], d1->point[1], d1->point[2], d2->point[0], d2->point[1], d2->point[2]);
  432.     }
  433.     else {
  434. /*    f1 = edgefaces[i][0];*/
  435.       f1 = bspMem->edgefaces[0][i];
  436. /*    f2 = edgefaces[i][1];*/
  437.       f2 = bspMem->edgefaces[1][i];
  438.       if (f1->planeside != f2->planeside)
  439.     continue;
  440.       if (f1->planenum != f2->planenum)
  441.     continue;
  442.  
  443.       // on the same plane, might be discardable
  444.       if (f1->texturenum == f2->texturenum) {
  445.     hvertex[edge->v[0]].numedges -= 2;
  446.     hvertex[edge->v[1]].numedges -= 2;
  447.     c_nonconvex++;
  448.       }
  449.       else
  450.     c_multitexture++;
  451.     }
  452.   }
  453.  
  454.   //      mprintf ("%5i edges\n", i);
  455.   //      mprintf ("%5i c_nonconvex\n", c_nonconvex);
  456.   //      mprintf ("%5i c_multitexture\n", c_multitexture);
  457.   //      CheckVertexes ();
  458. }
  459. #endif
  460.  
  461. /*
  462.  * ================
  463.  * MakeFaceEdges_r
  464.  * ================
  465.  */
  466. void MakeFaceEdges_r(__memBase, register struct node * node)
  467. {
  468.   struct visfacet *f;
  469.  
  470.   if (node->planenum == PLANENUM_LEAF)
  471.     return;
  472.  
  473.   for (f = node->faces; f; f = f->next)
  474.     FindFaceEdges(bspMem, f);
  475.  
  476.   MakeFaceEdges_r(bspMem, node->children[0]);
  477.   MakeFaceEdges_r(bspMem, node->children[1]);
  478. }
  479.  
  480. /*
  481.  * ================
  482.  * MakeFaceEdges
  483.  * ================
  484.  */
  485. void MakeFaceEdges(__memBase, struct node * headnode)
  486. {
  487.   mprintf("----- MakeFaceEdges -----\n");
  488.  
  489.   InitHash();
  490.   c_tryedges = 0;
  491.   c_cornerverts = 0;
  492.  
  493.   MakeFaceEdges_r(bspMem, headnode);
  494.  
  495.   //      CheckEdges ();
  496.  
  497.   GrowNodeRegions(bspMem, headnode);
  498.  
  499.   firstmodeledge = bspMem->numedges;
  500.   firstmodelface = bspMem->numfaces;
  501.   
  502.   /* added by niels */
  503.   kfree();
  504. }
  505.